#include <iostream>

template <class K, class E>
struct PairNode
{
    using PairType = std::pair<const K, E>;
    PairType element;
    PairNode<K,E>* next;

    PairNode(const PairType& thePair):element(thePair){}
    PairNode(const PairType& thePair, PairNode<K,E>* theNext):
        element(thePair){next=theNext;}
};

template <class K, class E>
class Dictionary
{
public:
    virtual ~Dictionary(){}
    virtual bool empty()const=0;
    virtual int size()const=0;
    virtual std::pair<const K,E>* find(const K& theKey)const=0;
    virtual void insert(const std::pair<K,E>& thePair)=0;
    virtual void erase(const K& theKey)=0;
};

template <class K, class E>
class SortedChain : public Dictionary<K,E>
{
public:
    SortedChain(){m_firstNode=nullptr; m_size=0;}
    virtual ~SortedChain();

    // ADT
    bool empty()const{return m_size==0;}
    int size()const{return m_size;}
    std::pair<const K,E>* find(const K& theKey)const;
    void insert(const std::pair<K,E>& thePair);
    void erase(const K& theKey);

    void output(std::ostream& out)const;
protected:
    PairNode<K,E>* m_firstNode;
    int m_size;
};

template <class K, class E>
std::pair<const K,E>* SortedChain<K,E>::find(const K& theKey)const
{
    PairNode<K,E>* current_node = m_firstNode;

    while (current_node != nullptr && current_node->element.first != theKey) {
        current_node = current_node->next;
    }

    if(current_node != nullptr && current_node->element.first == theKey){
        return &current_node->element;
    }else{
        return nullptr;
    }
}

template <class K, class E>
void SortedChain<K,E>::insert(const std::pair<K,E>& thePair)
{
    PairNode<K,E>* current_node = m_firstNode;
    PairNode<K,E>* last_node = nullptr;

    while (current_node != nullptr &&
           current_node->element.first < thePair.first) {
        last_node = current_node;
        current_node = current_node->next;
    }

    if(current_node != nullptr &&
            current_node->element.first == thePair.first){
        current_node->element.second = thePair.second;
        return;
    }

    PairNode<K,E>* node = new PairNode<K,E>(thePair, current_node);
    if(last_node == nullptr) m_firstNode = node;
    else last_node->next = node;

    m_size--;
    return;
}

template <class K, class E>
void SortedChain<K,E>::erase(const K& theKey)
{
    PairNode<K,E>* current_node = m_firstNode;
    PairNode<K,E>* last_node = nullptr;

    while (current_node != nullptr && current_node->element.first < theKey) {
        last_node = current_node;
        current_node = current_node->next;
    }

    if(current_node != nullptr && current_node->element.first == theKey){
        if(last_node == nullptr) m_firstNode = current_node->next;
        else last_node->next = current_node->next;
        delete current_node;
        m_size --;
    }

}

template <class K, class E>
SortedChain<K,E>::~SortedChain()
{
    while (m_firstNode != nullptr) {
        PairNode<K,E>* next = m_firstNode->next;
        delete m_firstNode;
        m_firstNode = next;
    }
}

template <class K, class E>
void SortedChain<K,E>::output(std::ostream& out)const
{
    PairNode<K,E>* current_node = m_firstNode;
    while (current_node != nullptr) {
        out<<"["<<current_node->element.first<<","
          <<current_node->element.second<<"]"<<std::endl;

        current_node = current_node->next;
    }
}


int main(int argc, char *argv[])
{
    using K = const int;
    using E = int;

    SortedChain<K,E> sortedChain;

    // insert
    std::pair<K,E> a(1,10);
    std::pair<K,E> b(2, 20);
    std::pair<K,E> c(3, 30);
    std::pair<K,E> d(4,40);
    sortedChain.insert(a);
    sortedChain.insert(b);
    sortedChain.insert(d);
    sortedChain.insert(c);
    sortedChain.output(std::cout);

    // erase
    sortedChain.erase(2);
    sortedChain.output(std::cout);

    return 0;
}

